package com.sicheng.lc.杂题.多路归并技巧之构造有序链表;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/15 17:28
 */
public class 寻找两个正序数组的中位数 {

    public static void main(String[] args) {

        寻找两个正序数组的中位数 s = new 寻找两个正序数组的中位数();
        int[] nums1 = {2, 4}, nums2 = {1, 3, 5, 6};
        System.out.println(s.findMedianSortedArrays(nums1, nums2));
    }

    // O(m+n)
    // lc恶心人要 O(log(m+n)) todo
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0) {
            if (nums2.length % 2 == 1)
                return nums2[nums2.length / 2];
            return (double) (nums2[nums2.length >> 1] + nums2[nums2.length - 1 >> 1]) / 2;
        }
        if (nums2.length == 0) {
            if (nums1.length % 2 == 1)
                return nums1[nums1.length / 2];
            return (double) (nums1[nums1.length >> 1] + nums1[nums1.length - 1 >> 1]) / 2;
        }
        int i = 0, j = 0;
        if (nums1[0] > nums2[0]) {
            int[] t = nums1;
            nums1 = nums2;
            nums2 = t;
        }

        int k;
        boolean ok = false;
        if ((nums1.length + nums2.length) % 2 == 1) {
            ok = true;
            k = nums1.length + nums2.length + 1 >> 1;
        } else {
            k = nums1.length + nums2.length >> 1;
        }
        int cnt = 1;
        int m = nums1[0], n = nums2[0];
        while (cnt < k && i < nums1.length - 1 && j < nums2.length) {

            while (cnt < k && i + 1 < nums1.length && nums1[i + 1] <= nums2[j]) {
                i++;
                cnt++;
                if (cnt == k) {
                    m = nums1[i];
                    if (i + 1 < nums1.length && nums1[i + 1] <= nums2[j]) {
                        n = nums1[i + 1];
                    } else {
                        n = nums2[j];
                    }
                }
            }

            while (cnt < k && j < nums2.length && i + 1 < nums1.length && nums1[i + 1] >= nums2[j]) {
                j++;
                cnt++;
                if (cnt == k) {
                    m = nums2[j - 1];
                    if (j < nums2.length && nums1[i + 1] >= nums2[j]) {
                        n = nums2[j];
                    } else {
                        n = nums1[i + 1];
                    }
                }
            }

        }

        while (cnt < k) {
            while (cnt < k && i < nums1.length - 1) {
                i++;
                cnt++;
                m = nums1[i];
                n = nums1[i + 1];
            }
            while (cnt < k && j < nums2.length) {
                j++;
                cnt++;
                m = nums2[j - 1];
                n = nums2[j];
            }
        }


        if (ok)
            return m;

        return (double) (m + n) / 2;
    }
}
